1. Field of the Invention
The present invention relates to a decoding apparatus and a decoding method and, particularly, to a decoding apparatus and a decoding method that perform decoding of tail-biting convolutional coded data using the Viterbi algorithm.
2. Description of Related Art
In a radio communication system such as a mobile communication system, communication is performed using data that is encoded in order to improve the error correction capability of data communicated by a radio signal. Convolutional coding is often used as an encoding technique. There are two types of convolutional coding: terminating convolutional coding and tail-biting convolutional coding.
The terminating convolutional coding generates encoded data by setting a termination bit having a predetermined value to the initial state of an encoder and at the end of a data row to be transmitted. Further, because the value of the initial state of the encoder is known in a decoder, the decoder performs decoding using the value of the initial state of the encoder as the initial state of the decoder at the start of decoding.
On the other hand, the tail-biting convolutional coding performs encoding and decoding of data without using the termination bit. The tail-biting technique performs encoding by setting the final K-1 (K is a constraint length) of a data row to be encoded as the initial value of an encoder. Thus, when data encoded by the tail-biting technique is decoded, the initial state and the final state of a decoder that performs the decoding are the same. Therefore, the decoder that decodes the data encoded by the tail-biting technique starts decoding processing with the initial state unknown, and determines the stop condition of the decoding processing with use of the characteristics of the data that the initial state and the end state are the same. The detail of the tail-biting decoding is disclosed in “On Tail Biting Convolutional Codes”, Howard H. Ma et al., IEEE Transactions on Communications, Vol. COM-34, No. 2, February, 1986. Further, a Viterbi decoding method and a Viterbi decoding circuit for decoding data that is encoded by the tail-biting technique are disclosed in U.S. Pat. No. 5,887,007 (Iwata et al.).
The Viterbi decoding method taught by Iwata et al. is described hereinafter. The Viterbi decoding circuit taught by Iwata et al. performs decoding by executing an add-compare-select (ACS) operation on received encoded data. The ACS operation calculates a path in the maximum likelihood state of a path trace indicating a state transition from the start state to the final state of decoded data that is obtained by decoding the encoded data. The maximum likelihood state is the state transition of decoded data that is most likely (i.e. that has the highest likelihood) to the state transition of an encoder when encoding data before encoding by the encoder.
FIG. 10 is a flowchart showing the Viterbi decoding method disclosed in Iwata et al. Referring to FIG. 10, the Viterbi decoding method taught by Iwata et al. first executes the ACS operation repeatedly to select a path at each time and update a path metric (Steps S101 and S102) Each time performing the ACS operation, information about which of paths that reach each state has been selected (path selection signal) is stored into a path memory
When the repetitive execution of the ACS operation ends on all the received bit rows, a maximum likelihood state Ss having a path metric with the highest likelihood at that time is detected (Step S103). By setting the maximum likelihood state Ss as the start state, path traceback is performed based on the path selection signal stored in the path memory to calculate a decoded bit from the state of each time that is traced back, thereby obtaining a decoded bit row A (Step S104). Further, a state Sr that is reached at the end of the traceback is detected (S105). After that, error check of the decoded bit row A is performed to determine whether there is an error in the decoded bit row A (Steps S106 and S107).
If the determination result shows that there is an error in the decoded bit row A, the maximum likelihood state Ss and the state Sr that is reached by the traceback are compared (Step S108). If the states Ss and Sr match, the process proceeds to Step S111, which is described later. If, on the other hand, the states Ss and Sr do not match, the state Sr is set as the start state, and path traceback is performed based on the path selection signal stored in the path memory to calculate a decoded bit from the state of each time that is traced back, thereby obtaining a decoded bit row B (Step S109). After that, error check of the decoded bit row B is performed to determine whether there is an error IN the decoded bit row B (Step S110).
On the other hand, if the determination result of Step S107 shows that there is no error in the decoded bit row A, if the determination result of Step S108 shows that the maximum likelihood state Ss and the trace finally reached state Sr match, or if error check on the decoded bit row B is completed, it is decided whether or not to use the obtained decoded bit row A or B as an output bit row, whether to use the obtained decoded bit row A or B after error correction, and so on, and then the output bit row is sent out (Step S111). For example, if there is no error in the decoded bit row A, the decoded bit row A may be used as the output bit row. If there is an error in the decoded bit row A and there is no error in the decoded bit row B, the decoded bit row B may be used as the output bit row. If there is an error in both of the decoded bit rows A and B, the output bit row may be decided according to a prescribed rule.
FIG. 11 is a state transition diagram to describe a specific example of the path traceback according to the Viterbi decoding method disclosed in Iwata et al. In the example of FIG. 11, it is assumed that an incorrect state 2 is selected as the maximum likelihood state, which is the state at the final time. In such a case, the Viterbi decoding method taught by Iwata et al. executes the path traceback of Step S104 starting from the state 2. In the traceback from the state 2, (10), a decoded bit “1” is obtained. Because the decoded bit (input bit) is “1” and a transition is made to the state 2,, the state at the previous time t=6, is the state 1, (01). Thus, a higher order bit “0” of the 2, bits that define the state is obtained as the next decoded bit.
Subsequently, decoded bits are obtained one after another in the same way, and when it is traced back to the time t=0, a decoded bit row “1011010” (arranged in the order of traceback) is obtained. If error check is executed on the decoded bit row “0101101” that is obtained as a result of performing the path traceback by setting the state 2,, which is not the correct state, as the maximum likelihood state, a result shows that there is an error (Steps S106, S107).
Therefore, the path traceback is executed by setting the finally reached state in the first path traceback (Step S104), which is the state 0 in this case, to the state of the final time t=7 (Step S109). Because the start state of the path traceback is the state 0, (00), “0” is obtained as the decoded bit. Further, because the state of the time t=7, is the state 0, and the bit (decoded bit) that makes a transition to the state 0, is “0”, the state at the time t=6, is the state 1, (01). Thus, “0” is obtained as the next decoded bit. Subsequently, decoded bits are obtained one after another in the same way, and when it is traced back to the time t=0, a decoded bit row “0011010” (arranged in the order of traceback) is obtained. If the order of the decoded bit row is returned to its original order, a decoded bit row that is the same as an input bit row to the encoder is obtained.
In this manner, the Viterbi decoding method taught by Iwata et al. executes path trace by setting the finally reached state as the start state when there is an error in a decoded signal obtained by path trace from a given state and the finally reached state and the start state of the path trace are different, and decides a finally output decoded signal by including the decoded signal obtained by the execution as a candidate. It is thereby possible to improve the accuracy (error rate) of the finally output decoded signal while preventing an increase in processing time and complication of the structure.
However, the present inventors have found a problem that, although the Viterbi decoding method taught by Iwata et al. performs additional traceback on a different path when a decoding result obtained by traceback on a maximum likelihood path is erroneous, it ends decoding if a decoding result obtained by the additional traceback is also erroneous, thus having low error correction capability.